/*
 * Kodkod -- Copyright (c) 2005-present, Emina Torlak
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 */
package kodkod.util.collections;

import java.util.AbstractMap;
import java.util.AbstractSet;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;

/**
 * A map with a fixed set of keys that acts as an indexer, assigning a unique
 * integer in the range [0..#keys) to each key. This class implements the
 * <tt>Map</tt> interface with an array, using reference-equality in place of
 * object-equality when comparing keys (and values). In other words, in a
 * <tt>FixedMap</tt>, two keys <tt>k1</tt> and <tt>k2</tt> are considered equal
 * if and only if <tt>(k1==k2)</tt>. (In normal <tt>Map</tt> implementations
 * (like <tt>HashMap</tt>) two keys <tt>k1</tt> and <tt>k2</tt> are considered
 * equal if and only if <tt>(k1==null ? k2==null : k1.equals(k2))</tt>.)
 * </p>
 * <p>
 * <b>This class is <i>not</i> a general-purpose <tt>Map</tt> implementation!
 * While this class implements the <tt>Map</tt> interface, it intentionally
 * violates <tt>Map's</tt> general contract, which mandates the use of the
 * <tt>equals</tt> method when comparing objects. </b>
 * </p>
 * <p>
 * This class provides {@link #put(Object, Object)} operation for the keys
 * within its fixed key set and permits <tt>null</tt> values and the
 * <tt>null</tt> key. The {@link #remove(Object)} operation is not supported.
 * This class guarantees that the order of the map will remain constant over
 * time.
 * </p>
 * <p>
 * This class provides log-time performance for the basic operations
 * (<tt>get</tt> and <tt>put</tt>), assuming the system identity hash function
 * ({@link System#identityHashCode(Object)}) disperses elements properly among
 * the buckets.
 * </p>
 * <p>
 * This implementation is not synchronized, and its iterators are not fail-fast.
 * </p>
 *
 * @specfield keys: set K
 * @specfield map: keys -> one V
 * @specfield indices: keys lone->one [0..#keys)
 * @author Emina Torlak
 */
public final class FixedMap<K, V> extends AbstractMap<K,V> implements Indexer<K> {

    private final Object[] keys;
    private final Object[] values;

    /**
     * Constructs a new fixed map from the given map.
     *
     * @ensures this.keys' = keys && this.map = map.map
     */
    public FixedMap(Map<K,V> map) {
        this(map.keySet());
        for (int i = 0, size = map.size(); i < size; i++) {
            values[i] = map.get(keys[i]);
        }
    }

    /**
     * Constructs a new fixed map for the given set of keys.
     *
     * @ensures this.keys' = keys && no this.map'
     */
    public FixedMap(Set<K> keys) {
        final int size = keys.size();
        this.keys = Containers.identitySort(keys.toArray(new Object[size]));
        values = new Object[size];
    }

    /**
     * Constructs a new fixed map, backed by the given array of keys. The provided
     * array must not contain duplicates, its entries must be sorted in the
     * increasing order of identity hashcodes, and it must not be modified while in
     * use by this map. The map will not behave correctly if these requirements are
     * violated.
     *
     * @requires no disj i, j: [0..keys.length) | keys[i] == keys[j]
     * @requires all i, j: [0..keys.length) | i < j =>
     *           System.identityHashCode(keys[i]) <=
     *           System.identityHashCode(keys[j])
     * @ensures this.keys' = keys && no this.map'
     */
    public FixedMap(K[] keys) {
        this.keys = keys;
        this.values = new Object[keys.length];
    }

    /**
     * Returns the index of the given key, if it is in this.keys. Otherwise returns
     * a negative number.
     *
     * @return key in this.keys => this.indices[key], {i: int | i < 0 }
     */
    @Override
    public final int indexOf(K key) {
        return Containers.identityBinarySearch(keys, key);
    }

    /**
     * Returns the key at the given index.
     *
     * @return this.indices.index
     * @throws IndexOutOfBoundsException index !in this.indices[this.keys]
     */
    @Override
    @SuppressWarnings("unchecked" )
    public final K keyAt(int index) {
        try {
            return (K) keys[index];
        } catch (ArrayIndexOutOfBoundsException e) {
            throw new IndexOutOfBoundsException();
        }
    }

    /**
     * Tests whether the specified object reference is a key in this fixed map.
     *
     * @return key in this.keys
     */
    @Override
    @SuppressWarnings("unchecked" )
    public final boolean containsKey(Object key) {
        return indexOf((K) key) >= 0;
    }

    /**
     * Tests whether the specified object reference is a value in this fixed map.
     *
     * @return value in this.map[this.keys]
     */
    @Override
    public final boolean containsValue(Object value) {
        for (Object o : values) {
            if (o == value)
                return true;
        }
        return false;
    }

    /**
     * Returns a set view of the mappings contained in this map. Each element in the
     * returned set is a reference-equality-based <tt>Map.Entry</tt>. The set is
     * backed by the map, so changes to the map are reflected in the set, and
     * vice-versa. If the map is modified while an iteration over the set is in
     * progress, the results of the iteration are undefined. The set does support
     * neither removal nor addition.
     * <p>
     * Like the backing map, the <tt>Map.Entry</tt> objects in the set returned by
     * this method define key and value equality as reference-equality rather than
     * object-equality. This affects the behavior of the <tt>equals</tt> and
     * <tt>hashCode</tt> methods of these <tt>Map.Entry</tt> objects. A
     * reference-equality based <tt>Map.Entry
     * e</tt> is equal to an object <tt>o</tt> if and only if <tt>o</tt> is a
     * <tt>Map.Entry</tt> and <tt>e.getKey()==o.getKey() &&
     * e.getValue()==o.getValue()</tt>. To accommodate these equals semantics, the
     * <tt>hashCode</tt> method returns <tt>System.identityHashCode(e.getKey()) ^
     * System.identityHashCode(e.getValue())</tt>.
     * <p>
     * <b>Owing to the reference-equality-based semantics of the <tt>Map.Entry</tt>
     * instances in the set returned by this method, it is possible that the
     * symmetry and transitivity requirements of the {@link Object#equals(Object)}
     * contract may be violated if any of the entries in the set is compared to a
     * normal map entry, or if the set returned by this method is compared to a set
     * of normal map entries (such as would be returned by a call to this method on
     * a normal map). However, the <tt>Object.equals</tt> contract is guaranteed to
     * hold among identity-based map entries, and among sets of such entries. </b>
     *
     * @return a set view of the identity-mappings contained in this map.
     */
    @Override
    public final Set<Map.Entry<K,V>> entrySet() {
        return new AbstractSet<Map.Entry<K,V>>() {

            @Override
            @SuppressWarnings("unchecked" )
            public boolean contains(Object o) {
                final Map.Entry<K,V> e = (Map.Entry<K,V>) o;
                final int index = FixedMap.this.indexOf(e.getKey());
                return index < 0 ? false : values[index] == e.getValue();
            }

            @Override
            public Iterator<java.util.Map.Entry<K,V>> iterator() {
                return new EntryIterator();
            }

            @Override
            public int size() {
                return keys.length;
            }

            @Override
            public Object[] toArray() {
                int size = size();
                Object[] result = new Object[size];
                for (int i = 0; i < size; i++)
                    result[i] = new Entry(i);
                return result;
            }

            @Override
            @SuppressWarnings("unchecked" )
            public <T> T[] toArray(T[] a) {
                int size = size();
                if (a.length < size)
                    a = (T[]) java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), size);
                for (int i = 0; i < size; i++)
                    a[i] = (T) new Entry(i);
                if (a.length > size)
                    a[size] = null;
                return a;
            }
        };
    }

    /**
     * Returns the value to which the specified key is mapped in this fixed map, or
     * <tt>null</tt> if the map contains no mapping for this key. A return value of
     * <tt>null</tt> does not <i>necessarily</i> indicate that the map contains no
     * mapping for the key; it is also possible that the map explicitly maps the key
     * to <tt>null</tt>. The <tt>containsKey</tt> method may be used to distinguish
     * these two cases.
     *
     * @return this.map[key]
     */
    @Override
    @SuppressWarnings("unchecked" )
    public final V get(Object key) {
        final int index = indexOf((K) key);
        return index < 0 ? null : (V) values[index];
    }

    /**
     * Returns the value to which the key at the specified index is mapped in this
     * fixed map.
     *
     * @requires index in this.indices[this.keys]
     * @return this.map[this.indices.index]
     * @throws IndexOutOfBoundsException index !in this.indices[this.keys]
     */
    @SuppressWarnings("unchecked" )
    public final V get(int index) {
        try {
            return (V) values[index];
        } catch (ArrayIndexOutOfBoundsException e) {
            throw new IndexOutOfBoundsException();
        }
    }

    /**
     * @see java.util.Map#isEmpty()
     */
    @Override
    public final boolean isEmpty() {
        return keys.length == 0;
    }

    /**
     * Associates the specified value with the specified key in this fixed map. If
     * the map previously contained a mapping for this key, the old value is
     * replaced. This method assumes that the given key is in the fixed keyset of
     * this map.
     *
     * @requires key in this.keys
     * @return this.map[key]
     * @ensures this.map' = this.map ++ key->value
     * @throws IllegalArgumentException key !in this.keys
     */

    @Override
    @SuppressWarnings("unchecked" )
    public final V put(K key, V value) {
        final int index = indexOf(key);
        if (index < 0)
            throw new IllegalArgumentException();
        final V oldValue = (V) values[index];
        values[index] = value;
        return oldValue;
    }

    /**
     * Throws an {@link UnsupportedOperationException} exception.
     *
     * @see java.util.Map#remove(java.lang.Object)
     */
    @Override
    public final V remove(Object key) {
        throw new UnsupportedOperationException();
    }

    /**
     * @see java.util.Map#size()
     */
    @Override
    public final int size() {
        return keys.length;
    }

    /**
     * Returns the hash code value for this map. The hash code of a map is defined
     * to be the sum of the hashcode of each entry in the map's entrySet view. This
     * ensures that <tt>t1.equals(t2)</tt> implies that
     * <tt>t1.hashCode()==t2.hashCode()</tt> for any two <tt>FixedMap</tt> instances
     * <tt>t1</tt> and <tt>t2</tt>, as required by the general contract of
     * {@link Object#hashCode()}.
     * <p>
     * <b>Owing to the reference-equality-based semantics of the <tt>Map.Entry</tt>
     * instances in the set returned by this map's <tt>entrySet</tt> method, it is
     * possible that the contractual requirement of <tt>Object.hashCode</tt>
     * mentioned in the previous paragraph will be violated if one of the two
     * objects being compared is an <tt>FixedMap</tt> instance and the other is a
     * normal map.</b>
     *
     * @return the hash code value for this map.
     * @see Object#hashCode()
     * @see Object#equals(Object)
     * @see #equals(Object)
     */
    @Override
    public int hashCode() {
        int result = 0;
        for (int i = 0; i < keys.length; i++)
            result += System.identityHashCode(keys[i]) ^ System.identityHashCode(values[i]);
        return result;
    }

    /**
     * Compares the specified object with this map for equality. Returns
     * <tt>true</tt> if the given object is also a map and the two maps represent
     * identical object-reference mappings. More formally, this map is equal to
     * another map <tt>m</tt> if and only if map
     * <tt>this.entrySet().equals(m.entrySet())</tt>.
     * <p>
     * <b>Owing to the reference-equality-based semantics of this map it is possible
     * that the symmetry and transitivity requirements of the <tt>Object.equals</tt>
     * contract may be violated if this map is compared to a normal map. However,
     * the <tt>Object.equals</tt> contract is guaranteed to hold among
     * <tt>FixedMap</tt> instances.</b>
     *
     * @param o object to be compared for equality with this map.
     * @return <tt>true</tt> if the specified object is equal to this map.
     * @see Object#equals(Object)
     */
    @Override
    public boolean equals(Object o) {
        if (o == this) {
            return true;
        } else if (o instanceof FixedMap) {
            FixedMap< ? , ? > m = (FixedMap< ? , ? >) o;
            if (m.size() != size())
                return false;
            for (int i = 0; i < keys.length; i++) {
                if (keys[i] != m.keys[i] || values[i] != m.values[i])
                    return false;
            }
            return true;
        } else if (o instanceof Map) {
            Map< ? , ? > m = (Map< ? , ? >) o;
            return entrySet().equals(m.entrySet());
        } else {
            return false; // o is not a Map
        }
    }

    private class Entry implements Map.Entry<K,V> {

        int index;

        Entry(int index) {
            this.index = index;
        }

        @Override
        @SuppressWarnings("unchecked" )
        public final K getKey() {
            return (K) keys[index];
        }

        @Override
        @SuppressWarnings("unchecked" )
        public final V getValue() {
            return (V) values[index];
        }

        @Override
        public V setValue(V value) {
            throw new UnsupportedOperationException();
        }

        @Override
        public int hashCode() {
            return System.identityHashCode(keys[index]) ^ System.identityHashCode(values[index]);
        }

        @Override
        public boolean equals(Object o) {
            if (o instanceof Map.Entry) {
                final Map.Entry< ? , ? > e = (Map.Entry< ? , ? >) o;
                return keys[index] == e.getKey() && values[index] == e.getValue();
            } else
                return false;
        }

        @Override
        public String toString() {
            return keys[index] + "=" + values[index];
        }
    }

    private final class EntryIterator extends Entry implements Iterator<Map.Entry<K,V>> {

        int next = 0;

        EntryIterator() {
            super(-1);
        }

        @Override
        @SuppressWarnings("unchecked" )
        public V setValue(V value) {
            final V oldValue = (V) values[index];
            values[index] = value;
            return oldValue;
        }

        @Override
        public boolean hasNext() {
            return next < keys.length;
        }

        @Override
        public Map.Entry<K,V> next() {
            if (!hasNext())
                throw new NoSuchElementException();
            index = next++;
            return this;
        }

        @Override
        public int hashCode() {
            return index < 0 ? System.identityHashCode(this) : super.hashCode();
        }

        @Override
        public boolean equals(Object o) {
            return index < 0 ? this == o : super.equals(o);
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }

        @Override
        public String toString() {
            return index < 0 ? "[]" : super.toString();
        }
    }
}
